// 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

// 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

// s = s1 + s2 + ... + sn
// t = t1 + t2 + ... + tm
// |n - m| <= 1
// 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
// 注意：a + b 意味着字符串 a 和 b 连接。

// 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
// 输出：true
// 示例 2：

// 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
// 输出：false
// 示例 3：

// 输入：s1 = "", s2 = "", s3 = ""
// 输出：true

var maxLen = function (s1, s2) {
  const max = Math.max(s1.length, s2.length);
  for (let n = 0; n < max; n++) {
    if (s1[n] !== s2[n]) return n;
  }
  return max;
};

var getUps = function (arr) {
  let ans = arr[0].map((item) => [item]);
  let k = 1;
  console.time("1");
  while (k++ < arr.length) {
    const rights = arr[k - 1];
    let _ans = [];
    for (let n = 0; n < ans.length; n++) {
      const lefts = ans[n];
      if (lefts.at(-1) > rights.at(-1)) {
        continue;
      }
      for (let m = 0; m < rights.length; m++) {
        const right = rights[m];
        if (right > lefts.at(-1)) {
          // 不判断则是全量的，过滤得到数组是升序的
          _ans.push([...lefts, right]);
        }
      }
    }
    ans = _ans;
  }
  console.timeEnd("1");
  return ans;
};
// 超出时间限制
var isInterleave = function (s1, s2, s3) {
  if (s1.length + s2.length !== s3.length) return false;
  if (!s1) return s2 === s3;
  if (!s2) return s1 === s3;

  const ans = []; // 先将s1的每一个元素在s3中的全部位置情况
  //   console.time("2");
  const map = {};
  for (let left = 0; left < s1.length; left++) {
    const _left = s1[left];

    const _ans = [];
    for (let right = 0; right < s3.length; right++) {
      const _right = s3[right];
      if (_left === _right) {
        _ans.push(right);
      }
    }
    ans.push(_ans.slice(map[_left] || 0)); // 优化，减少出现过的长度
    map[_left] = (map[_left] || 0) + 1;
  }
  //   console.timeEnd("2");
  //   console.log("ans: ", ans);
  //   得到如下的数组，再
  //   [
  //     [0, 1, 8],
  //     [0, 1, 8],
  //     [3, 4, 6],
  //     [5, 7, 9],
  //     [5, 7, 9],
  //   ];
  // 通过getUps方法得到如下数组，将二维数组的每一个数组中取一个元素，得到若干个升序的数组
  //   [
  //     [0, 1, 3, 5, 7],
  //     [0, 1, 3, 5, 9],
  //     [0, 1, 3, 7, 9],
  //     [0, 1, 4, 5, 7],
  //     [0, 1, 4, 5, 9],
  //     [0, 1, 4, 7, 9],
  //     [0, 1, 6, 7, 9],
  //   ];
  // 再按二维数组的每一个数组剔除s3的元素，最终判断得到的字符串是否和s2是否相等
  if (ans.length === 0) return true;
  const ups = getUps(ans);
  //   console.log("ups: ", JSON.stringify(ups));
  if (ups.length === 0) return false;

  for (const elements of ups) {
    let ans = s3;
    for (let i = 0; i < elements.length; i++) {
      const index = elements[i];
      ans = ans.slice(0, index - i) + ans.slice(index - i + 1); // 当移除一个元素之后，需要往前面走一位
    }
    if (ans === s2) return true;
  }

  return false;
};
// console.time();

const ans = isInterleave(
  "aaaaaabbbbbbbcccccccc",
  "aaaaaabbbbbbbcccccccc",
  "aaaaaabbbbbbbccccccccaaaaaabbbbbbbcccccccc"
);
// const ans = isInterleave(
//   "cbaccbbaabbacbaaabbcbccb",
//   "bbcaccccbabbbabbcaccacaaa",
//   "bcbaccbbbcaabbabacccabacabbaacbbbccbbabbcaccacaac"
// );
console.log("ans: ", ans);
// console.timeEnd();
